package 牛客.动态规划;

public class 力扣96不同的二叉搜索树 {
    public int numTrees(int n) {
        if (n==1 ||n==2) {
            return n;
        }
        int[] dp=new int[n+1];
        //dp[i]表示 当前i个节点能构成几种不同的二叉搜索树
        dp[0]=1;//这个定义，单纯为了左右子数节点为0时
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <dp.length ; i++) {
            for (int j = 1; j <=i ; j++) {
                dp[i] += dp[j-1]*dp[i-j];//j代表当前根节点，j-1代表左子树的节点个数，i-j代表右子树的节点个数
            }
        }
        return dp[n];

    }
}
